Section: New Results

Graph-Coloring and Treescan Register Allocation Using Repairing

Participants : Quentin Colombet, Benoit Boissinot, Philip Brisk [University of California, Riverside] , Sebastian Hack [Saarland University] , Fabrice Rastello.

Graph coloring and linear scan are two appealing techniques for register allocation as the underlying formalism are extremely clean and simple. Our previous work advocated the use of a decoupled approach that first lowers the register pressure by spilling variables, then performs live-range splitting, coalescing, and coloring in a separate phase. This enables the design of simpler, cleaner, and more efficient register allocators.

In this context, we introduced a new and more general approach to deal with register constraints. This approach, called repairing, does not require any preliminary live-range splitting and does not introduce additional spill code. It ignores register constraints during coloring/coalescing and repairs the violated constraints afterwards. We applied this method to develop both a graph-based and a scan-based decoupled approach: one based on the iterated register coalescer (IRC) and the other on a scan algorithm (the treescan) that uses static single assignment (SSA) properties.

Our experimental evaluation shows that, for the graph-based approach, we reduced the number of vertices (edges) in the interference graph by 26% (33%) without compromising the quality of the generated code. The treescan algorithm improved the compile time of the allocation process by $6.97\times$ over IRC while providing comparable results for the quality of the generated code.

This work was part of a collaboration with the Saarland University and the University of California, Riverside. It has been presented at the conference CASES'11 [7] .